﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_28_StrStr
{
    //实现 strStr() 函数。
    //Compelte
    class MainProject
    {
        static void Main(string[] args)
        {
            Console.WriteLine(StrStr("hello", "ll"));
            Console.WriteLine(StrStr("aaaaa", "bba"));
            Console.WriteLine(StrStr("", ""));
            Console.WriteLine(StrStr("aaa", "aaaa"));
            Console.WriteLine(StrStr("mississippi", "issipi"));
            Console.WriteLine(StrStr("a", "a"));
            Console.ReadKey();
        }
        public static int StrStr(string haystack, string needle)
        {
            if (needle.Length> haystack.Length)
            {
                return -1;
            }

            if (needle.Equals(""))
            {
                return 0;
            }

            Queue<int> vs = new Queue<int>();

            for (int i = 0; i < haystack.Length; i++)
            {
                if (haystack[i] == needle[0])
                {
                    vs.Enqueue(i);
                }
            }
            while (vs.Count>0)
            {
                int index = vs.Dequeue();
                if (haystack.Length - index < needle.Length)
                {
                    return -1;
                }
                string intercept = haystack.Substring(index, needle.Length);
                if (needle.Equals(intercept))
                {
                    return index;
                }
            }

            return -1;
        }
    }
}
